//给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。 
//
// 同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人： 
//
// 
// 总共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。 
// 在每一轮雇佣中，从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的
//一位工人。 
// 
// 比方说，costs = [3,2,7,7,1,2] 且 candidates = 2 ，第一轮雇佣中，我们选择第 4 位工人，因为他的代价最小 [3,2,
//7,7,1,2] 。 
// 第二轮雇佣，我们选择第 1 位工人，因为他们的代价与第 4 位工人一样都是最小代价，而且下标更小，[3,2,7,7,2] 。注意每一轮雇佣后，剩余工人的下
//标可能会发生变化。 
// 
// 如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。 
// 一位工人只能被选择一次。 
// 
//
// 返回雇佣恰好 k 位工人的总代价。 
//
// 
//
// 示例 1： 
//
// 输入：costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
//输出：11
//解释：我们总共雇佣 3 位工人。总代价一开始为 0 。
//- 第一轮雇佣，我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 ，有两位工人，我们选择下标更小的一位工人，即第 3 位工人
//。总代价是 0 + 2 = 2 。
//- 第二轮雇佣，我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 ，下标为 4 ，总代价是 2 + 2 = 4 。
//- 第三轮雇佣，我们从 [17,12,10,7,11,20,8] 中选择，最小代价是 7 ，下标为 3 ，总代价是 4 + 7 = 11 。注意下标为 3 
//的工人同时在最前面和最后面 4 位工人中。
//总雇佣代价是 11 。
// 
//
// 示例 2： 
//
// 输入：costs = [1,2,4,1], k = 3, candidates = 3
//输出：4
//解释：我们总共雇佣 3 位工人。总代价一开始为 0 。
//- 第一轮雇佣，我们从 [1,2,4,1] 中选择。最小代价为 1 ，有两位工人，我们选择下标更小的一位工人，即第 0 位工人，总代价是 0 + 1 = 1
// 。注意，下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。
//- 第二轮雇佣，我们从 [2,4,1] 中选择。最小代价为 1 ，下标为 2 ，总代价是 1 + 1 = 2 。
//- 第三轮雇佣，少于 3 位工人，我们从剩余工人 [2,4] 中选择。最小代价是 2 ，下标为 0 。总代价为 2 + 2 = 4 。
//总雇佣代价是 4 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= costs.length <= 105 
// 1 <= costs[i] <= 10⁵ 
// 1 <= k, candidates <= costs.length 
// 
//
// Related Topics 数组 双指针 模拟 堆（优先队列） 👍 49 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author ldltd
 * @date 2023-10-04 17:30:24
 * @description 2462.雇佣 K 位工人的总代价
 */
public class TotalCostToHireKWorkers{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new TotalCostToHireKWorkers().new Solution();
		//solution.totalCost(new int[]{28,35,21,13,21,72,35,52,74,92,25,65,77,1,73,32,43,68,8,100,84,80,14,88,42,53,98,69,64,40,60,23,99,83,5,21,76,34},32,12);
//		 solution.totalCost(new int[]{1,2,4,1},3,3);
		 solution.totalCost(new int[]{69,10,63,24,1,71,55,46,4,61,78,21,85,52,83,77,42,21,73,2,80,99,98,89,55,94,63,50,43,62,14},21,31);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
		//保存代价和序号，如果代价相同，用序号排序
		PriorityQueue<Integer[]> minheap = new PriorityQueue<>((o1, o2) -> {
			if(o1[0].equals(o2[0])) return o1[1]-o2[1];
			return o1[0]-o2[0];
		});
		int n = costs.length;
		int l=-1,r=n;
		long res=0;
		//如果两个都没到candidates，就先加入
		for (int i = 1; i <=k; i++) {
				while (l+1<=r&&l+1<candidates){
					l++;
					minheap.offer(new Integer[]{costs[l],l}) ;
				}
				//防止重复加入，当l=r-1时，r就不重复加入了
				while (l<r-1&&n-r<candidates) {
					r--;
					minheap.offer(new Integer[]{costs[r],r}) ;
				}
			if (!minheap.isEmpty()) {
				Integer[] poll = minheap.poll();
				res += poll[0];
				//因为是先判断后，再加入，所以每个下标的值都已经加入了
				//所以条件是l+1<r
				//判断加入的值在左边还是右边
				if (l+1<r&&poll[1] <= l) {
					l++;
					minheap.offer(new Integer[]{costs[l],l}) ;
				} else if(l+1<r) {
					r--;
					minheap.offer(new Integer[]{costs[r],r}) ;
				}
			}
		}
		return res;
	}

	/*两个优先队列*/
	public long totalCost1(int[] costs, int k, int candidates) {
		Queue<Integer> left = new PriorityQueue<>();
		Queue<Integer> right = new PriorityQueue<>();
		int n=costs.length;
		long res=0;
		//如果第一次candidates不能覆盖全部
		if(n>candidates*2){
			//先加入
			for(int i=0;i<candidates;i++){
				left.add(costs[i]);
			}
			for(int i=n-1;i>=n-candidates;i--){
				right.add(costs[i]);
			}
			//用两个指针来控制两个队列
			int l=candidates;
			int r=n-candidates-1;
			for(int i=0;i<k;i++){
				int a=999999999;
				int b=999999999;
				//取出最小堆的两个元素
				if(left.peek()!=null)a=left.peek();
				if(right.peek()!=null)b=right.peek();
				//System.out.println(a+" "+b);
				//加上最小的那个
				if(a<=b){
					res+=a;
					left.poll();
					//如果此时还没有加入完，lr没有相遇，就扩大边界
					if(l<=r){
						left.add(costs[l]);
						l++;
					}
				}
				else{
					res+=b;
					right.poll();
					if(l<=r){
						right.add(costs[r]);
						r--;
					}
				}

			}
		}
		else{
			//如果第一次就加入完了，则直接排序后按顺序加入
			Arrays.sort(costs);
			for(int i=0;i<k;i++){
				res+=costs[i];
			}
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
